package com.gitee.wsl.struct.tree.sample.color

import com.gitee.wsl.base.Option
import com.gitee.wsl.base.Tuple
import com.gitee.wsl.base.Tuple2
import com.gitee.wsl.base.Tuple3
import com.gitee.wsl.base.none
import com.gitee.wsl.base.of
import com.gitee.wsl.base.some

internal interface RedBlackTreeModule {
    /**
     * A non-empty tree node.
     *
     * @param <T> Component type
    </T> */
    class Node<T> internal constructor(
        val color: RedBlackTree.Color,
        val blackHeight: Int,
        val left: RedBlackTree<T>,
        val value: T,
        val right: RedBlackTree<T>,
        val empty: Empty<T>,
    ) : RedBlackTree<T> {
        val size: Int = left.size() + right.size() + 1

        override fun color(): RedBlackTree.Color {
            return color
        }

        override fun comparator(): Comparator<T> {
            return empty.comparator
        }

        override fun contains(value: T): Boolean {
            val result: Int = empty.comparator.compare(value, this.value)
            return if (result < 0) {
                left.contains(value)
            } else if (result > 0) {
                right.contains(value)
            } else {
                true
            }
        }

        override fun emptyInstance(): Empty<T> {
            return empty
        }

        override fun find(value: T): Option<T> {
            val result: Int = empty.comparator.compare(value, this.value)
            return if (result < 0) {
                left.find(value)
            } else if (result > 0) {
                right.find(value)
            } else {
                Option.some(this.value)
            }
        }

        override val isEmpty get() = false

//        override fun isEmpty(): Boolean {
//            return false
//        }

        override fun left(): RedBlackTree<T> {
            return left
        }

        override fun right(): RedBlackTree<T> {
            return right
        }

        override fun size(): Int {
            return size
        }

        override fun value(): T {
            return value
        }

        override fun toString(): String {
            return if (isLeaf) "($color:$value)" else toLispString(
                this
            )
        }

        private val isLeaf: Boolean
            get() = left.isEmpty && right.isEmpty

        fun color(color: RedBlackTree.Color): Node<T> {
            return if ((this.color == color)) this else Node(
                color,
                blackHeight,
                left,
                value,
                right,
                empty
            )
        }

        companion object {

            private fun toLispString(tree: RedBlackTree<*>): String {
                if (tree.isEmpty) {
                    return ""
                } else {
                    val node = tree as Node<*>
                    val value = node.color.toString() + ":" + node.value
                    if (node.isLeaf) {
                        return value
                    } else {
                        val left = if (node.left.isEmpty) "" else " " + toLispString(node.left)
                        val right = if (node.right.isEmpty) "" else " " + toLispString(node.right)
                        return "($value$left$right)"
                    }
                }
            }

            fun <T> color(tree: RedBlackTree<T>, color: RedBlackTree.Color?): RedBlackTree<T> {
                return if (tree.isEmpty) tree else (tree as Node<T>).color(color!!)
            }

            private fun <T> balanceLeft(
                color: RedBlackTree.Color, blackHeight: Int, left: RedBlackTree<T>, value: T,
                right: RedBlackTree<T>, empty: Empty<T>,
            ): Node<T> {
                if (color == RedBlackTree.Color.BLACK) {
                    if (!left.isEmpty) {
                        val ln = left as Node<T>
                        if (ln.color == RedBlackTree.Color.RED) {
                            if (!ln.left.isEmpty) {
                                val lln = ln.left as Node<T>
                                if (lln.color == RedBlackTree.Color.RED) {
                                    val newLeft = Node<T>(
                                        RedBlackTree.Color.BLACK, blackHeight, lln.left, lln.value, lln.right,
                                        empty
                                    )
                                    val newRight =
                                        Node<T>(RedBlackTree.Color.BLACK, blackHeight, ln.right, value, right, empty)
                                    return Node<T>(
                                        RedBlackTree.Color.RED,
                                        blackHeight + 1,
                                        newLeft,
                                        ln.value,
                                        newRight,
                                        empty
                                    )
                                }
                            }
                            if (!ln.right.isEmpty) {
                                val lrn = ln.right as Node<T>
                                if (lrn.color == RedBlackTree.Color.RED) {
                                    val newLeft = Node<T>(
                                        RedBlackTree.Color.BLACK, blackHeight, ln.left, ln.value, lrn.left,
                                        empty
                                    )
                                    val newRight =
                                        Node<T>(RedBlackTree.Color.BLACK, blackHeight, lrn.right, value, right, empty)
                                    return Node<T>(
                                        RedBlackTree.Color.RED,
                                        blackHeight + 1,
                                        newLeft,
                                        lrn.value,
                                        newRight,
                                        empty
                                    )
                                }
                            }
                        }
                    }
                }
                return Node(color, blackHeight, left, value, right, empty)
            }

            private fun <T> balanceRight(
                color: RedBlackTree.Color, blackHeight: Int, left: RedBlackTree<T>, value: T,
                right: RedBlackTree<T>, empty: Empty<T>,
            ): Node<T> {
                if (color == RedBlackTree.Color.BLACK) {
                    if (!right.isEmpty) {
                        val rn = right as Node<T>
                        if (rn.color == RedBlackTree.Color.RED) {
                            if (!rn.right.isEmpty) {
                                val rrn = rn.right as Node<T>
                                if (rrn.color == RedBlackTree.Color.RED) {
                                    val newLeft =
                                        Node<T>(RedBlackTree.Color.BLACK, blackHeight, left, value, rn.left, empty)
                                    val newRight = Node<T>(
                                        RedBlackTree.Color.BLACK, blackHeight, rrn.left, rrn.value, rrn.right,
                                        empty
                                    )
                                    return Node<T>(
                                        RedBlackTree.Color.RED,
                                        blackHeight + 1,
                                        newLeft,
                                        rn.value,
                                        newRight,
                                        empty
                                    )
                                }
                            }
                            if (!rn.left.isEmpty) {
                                val rln = rn.left as Node<T>
                                if (rln.color == RedBlackTree.Color.RED) {
                                    val newLeft =
                                        Node<T>(RedBlackTree.Color.BLACK, blackHeight, left, value, rln.left, empty)
                                    val newRight = Node<T>(
                                        RedBlackTree.Color.BLACK, blackHeight, rln.right, rn.value, rn.right,
                                        empty
                                    )
                                    return Node<T>(
                                        RedBlackTree.Color.RED,
                                        blackHeight + 1,
                                        newLeft,
                                        rln.value,
                                        newRight,
                                        empty
                                    )
                                }
                            }
                        }
                    }
                }
                return Node(color, blackHeight, left, value, right, empty)
            }

            private fun <T> blackify(tree: RedBlackTree<T>): Tuple2<out RedBlackTree<T>, Boolean> {
                if (tree is Node<*>) {
                    val node = tree as Node<T>
                    if (node.color == RedBlackTree.Color.RED) {
                        return Tuple.of(node.color(RedBlackTree.Color.BLACK), false)
                    }
                }
                return Tuple.of(tree, true)
            }

            fun <T> delete(tree: RedBlackTree<T>, value: T): Tuple2<out RedBlackTree<T>, Boolean> {
                if (tree.isEmpty) {
                    return Tuple.of(tree, false)
                } else {
                    val node = tree as Node<T>
                    val comparison: Int = node.comparator().compare(value, node.value)
                    if (comparison < 0) {
                        val deleted: Tuple2<out RedBlackTree<T>, Boolean> = delete(node.left, value)
                        val l: RedBlackTree<T> = deleted.first
                        val d: Boolean = deleted.second
                        if (d) {
                            return unbalancedRight(
                                node.color, node.blackHeight - 1, l, node.value, node.right,
                                node.empty
                            )
                        } else {
                            val newNode = Node(
                                node.color, node.blackHeight, l, node.value, node.right,
                                node.empty
                            )
                            return Tuple.of(newNode, false)
                        }
                    } else if (comparison > 0) {
                        val deleted: Tuple2<out RedBlackTree<T>, Boolean> =
                            delete(node.right, value)
                        val r: RedBlackTree<T> = deleted.first
                        val d: Boolean = deleted.second
                        if (d) {
                            return unbalancedLeft(
                                node.color, node.blackHeight - 1, node.left, node.value, r,
                                node.empty
                            )
                        } else {
                            val newNode = Node(
                                node.color, node.blackHeight, node.left, node.value, r,
                                node.empty
                            )
                            return Tuple.of(newNode, false)
                        }
                    } else {
                        if (node.right.isEmpty) {
                            return if (node.color == RedBlackTree.Color.BLACK) {
                                blackify<T>(node.left)
                            } else {
                                Tuple.of(node.left, false)
                            }
                        } else {
                            val nodeRight = node.right as Node<T>
                            val newRight: Tuple3<out RedBlackTree<T>, Boolean, T> =
                                deleteMin(nodeRight)
                            val r: RedBlackTree<T> = newRight.first
                            val d: Boolean = newRight.second
                            val m: T = newRight.third
                            if (d) {
                                return unbalancedLeft(
                                    node.color,
                                    node.blackHeight - 1,
                                    node.left,
                                    m,
                                    r,
                                    node.empty
                                )
                            } else {
                                val newNode: RedBlackTree<T> = Node(
                                    node.color, node.blackHeight, node.left, m, r,
                                    node.empty
                                )
                                return Tuple.of(newNode, false)
                            }
                        }
                    }
                }
            }

            private  fun <T> deleteMin(node: Node<T>): Tuple3<out RedBlackTree<T>, Boolean, T> {
                if (node.color() == RedBlackTree.Color.BLACK && node.left().isEmpty && node.right.isEmpty) {
                    return Tuple3<RedBlackTree<T>, Boolean, T>(node.empty, true, node.value())
                } else if (node.color() == RedBlackTree.Color.BLACK && node.left().isEmpty && node.right()
                        .color() == RedBlackTree.Color.RED
                ) {
                    return Tuple3<RedBlackTree<T>, Boolean, T>(
                        (node.right() as Node<T>).color(
                            RedBlackTree.Color.BLACK
                        ), false, node.value()
                    )
                } else if (node.color() == RedBlackTree.Color.RED && node.left().isEmpty) {
                    return Tuple3<RedBlackTree<T>, Boolean, T>(node.right(), false, node.value())
                } else {
                    val nodeLeft = node.left as Node<T>
                    val newNode: Tuple3<out RedBlackTree<T>, Boolean, T> = deleteMin(nodeLeft)
                    val l: RedBlackTree<T> = newNode.first
                    val deleted: Boolean = newNode.second
                    val m: T = newNode.third
                    if (deleted) {
                        val tD: Tuple2<Node<T>, Boolean> = unbalancedRight(
                            node.color, node.blackHeight - 1, l,
                            node.value, node.right, node.empty
                        )
                        return Tuple3<RedBlackTree<T>, Boolean, T>(tD.first, tD.second, m)
                    } else {
                        val tD = Node(
                            node.color,
                            node.blackHeight,
                            l,
                            node.value,
                            node.right,
                            node.empty
                        )
                        return Tuple3<RedBlackTree<T>, Boolean, T>(tD, false, m)
                    }
                }
            }

            fun <T> insert(tree: RedBlackTree<T>, value: T): Node<T> {
                if (tree.isEmpty) {
                    val empty = tree as Empty<T>
                    return Node<T>(RedBlackTree.Color.RED, 1, empty, value, empty, empty)
                } else {
                    val node = tree as Node<T>
                    val comparison: Int = node.comparator().compare(value, node.value)
                    if (comparison < 0) {
                        val newLeft = insert(node.left, value)
                        return if ((newLeft == node.left))
                            node
                        else
                            balanceLeft(
                                node.color, node.blackHeight, newLeft, node.value, node.right,
                                node.empty
                            )
                    } else if (comparison > 0) {
                        val newRight = insert(node.right, value)
                        return if ((newRight == node.right))
                            node
                        else
                            balanceRight(
                                node.color, node.blackHeight, node.left, node.value, newRight,
                                node.empty
                            )
                    } else {
                        // DEV-NOTE: Even if there is no _comparison_ difference, the object may not be _equal_.
                        //           To save an equals() call, which may be expensive, we return a new instance.
                        return Node(
                            node.color,
                            node.blackHeight,
                            node.left,
                            value,
                            node.right,
                            node.empty
                        )
                    }
                }
            }

            private fun isRed(tree: RedBlackTree<*>): Boolean {
                return !tree.isEmpty && (tree as Node<*>).color == RedBlackTree.Color.RED
            }

            fun <T> join(t1: RedBlackTree<T>, value: T, t2: RedBlackTree<T>): RedBlackTree<T> {
                if (t1.isEmpty) {
                    return t2.insert(value)
                } else if (t2.isEmpty) {
                    return t1.insert(value)
                } else {
                    val n1 = t1 as Node<T>
                    val n2 = t2 as Node<T>
                    val comparison = n1.blackHeight - n2.blackHeight
                    return if (comparison < 0) {
                        joinLT<T>(n1, value, n2, n1.blackHeight).color(RedBlackTree.Color.BLACK)
                    } else if (comparison > 0) {
                        joinGT<T>(n1, value, n2, n2.blackHeight).color(RedBlackTree.Color.BLACK)
                    } else {
                        Node<T>(RedBlackTree.Color.BLACK, n1.blackHeight + 1, n1, value, n2, n1.empty)
                    }
                }
            }

            private fun <T> joinGT(n1: Node<T>, value: T, n2: Node<T>, h2: Int): Node<T> {
                if (n1.blackHeight == h2) {
                    return Node<T>(RedBlackTree.Color.RED, h2 + 1, n1, value, n2, n1.empty)
                } else {
                    val node = joinGT(n1.right as Node<T>, value, n2, h2)
                    return balanceRight(n1.color, n1.blackHeight, n1.left, n1.value, node, n2.empty)
                }
            }

            private fun <T> joinLT(n1: Node<T>, value: T, n2: Node<T>, h1: Int): Node<T> {
                if (n2.blackHeight == h1) {
                    return Node<T>(RedBlackTree.Color.RED, h1 + 1, n1, value, n2, n1.empty)
                } else {
                    val node = joinLT(n1, value, n2.left as Node<T>, h1)
                    return balanceLeft(n2.color, n2.blackHeight, node, n2.value, n2.right, n2.empty)
                }
            }

            fun <T> merge(t1: RedBlackTree<T>, t2: RedBlackTree<T>): RedBlackTree<T> {
                if (t1.isEmpty) {
                    return t2
                } else if (t2.isEmpty) {
                    return t1
                } else {
                    val n1 = t1 as Node<T>
                    val n2 = t2 as Node<T>
                    val comparison = n1.blackHeight - n2.blackHeight
                    if (comparison < 0) {
                        val node = mergeLT(n1, n2, n1.blackHeight)
                        return color<T>(node, RedBlackTree.Color.BLACK)
                    } else if (comparison > 0) {
                        val node = mergeGT(n1, n2, n2.blackHeight)
                        return color<T>(node, RedBlackTree.Color.BLACK)
                    } else {
                        val node = mergeEQ(n1, n2)
                        return color<T>(node, RedBlackTree.Color.BLACK)
                    }
                }
            }

            private fun <T> mergeEQ(n1: Node<T>, n2: Node<T>): Node<T> {
                val m = minimum(n2)
                val t2: RedBlackTree<T> = deleteMin(n2).first
                val h2 = if (t2.isEmpty) 0 else (t2 as Node<T>).blackHeight
                if (n1.blackHeight == h2) {
                    return Node<T>(RedBlackTree.Color.RED, n1.blackHeight + 1, n1, m, t2, n1.empty)
                } else if (isRed(n1.left)) {
                    val node = Node<T>(RedBlackTree.Color.BLACK, n1.blackHeight, n1.right, m, t2, n1.empty)
                    return Node<T>(
                        RedBlackTree.Color.RED,
                        n1.blackHeight + 1,
                        color<T>(n1.left, RedBlackTree.Color.BLACK),
                        n1.value,
                        node,
                        n1.empty
                    )
                } else if (isRed(n1.right)) {
                    val rl = (n1.right as Node<T>).left
                    val rx = n1.right.value
                    val rr = n1.right.right
                    val left = Node<T>(RedBlackTree.Color.RED, n1.blackHeight, n1.left, n1.value, rl, n1.empty)
                    val right = Node<T>(RedBlackTree.Color.RED, n1.blackHeight, rr, m, t2, n1.empty)
                    return Node<T>(RedBlackTree.Color.BLACK, n1.blackHeight, left, rx, right, n1.empty)
                } else {
                    return Node<T>(RedBlackTree.Color.BLACK, n1.blackHeight, n1.color(RedBlackTree.Color.RED), m, t2, n1.empty)
                }
            }

            private fun <T> mergeGT(n1: Node<T>, n2: Node<T>, h2: Int): Node<T> {
                if (n1.blackHeight == h2) {
                    return mergeEQ(n1, n2)
                } else {
                    val node = mergeGT(n1.right as Node<T>, n2, h2)
                    return balanceRight(n1.color, n1.blackHeight, n1.left, n1.value, node, n1.empty)
                }
            }

            private fun <T> mergeLT(n1: Node<T>, n2: Node<T>, h1: Int): Node<T> {
                if (n2.blackHeight == h1) {
                    return mergeEQ(n1, n2)
                } else {
                    val node = mergeLT(n1, n2.left as Node<T>, h1)
                    return balanceLeft(n2.color, n2.blackHeight, node, n2.value, n2.right, n2.empty)
                }
            }

            fun <T> maximum(node: Node<T>): T {
                var curr = node
                while (!curr.right.isEmpty) {
                    curr = curr.right as Node<T>
                }
                return curr.value
            }

            fun <T> minimum(node: Node<T>): T {
                var curr = node
                while (!curr.left.isEmpty) {
                    curr = curr.left as Node<T>
                }
                return curr.value
            }

            fun <T> split(
                tree: RedBlackTree<T>,
                value: T,
            ): Tuple2<RedBlackTree<T>, RedBlackTree<T>> {
                if (tree.isEmpty) {
                    return Tuple.of(tree, tree)
                } else {
                    val node = tree as Node<T>
                    val comparison: Int = node.comparator().compare(value, node.value)
                    if (comparison < 0) {
                        val split: Tuple2<RedBlackTree<T>, RedBlackTree<T>> =
                            split(node.left, value)
                        return Tuple.of(
                            split.first,
                            join<T>(split.second, node.value, color<T>(node.right,
                                RedBlackTree.Color.BLACK
                            ))
                        )
                    } else if (comparison > 0) {
                        val split: Tuple2<RedBlackTree<T>, RedBlackTree<T>> =
                            split(node.right, value)
                        return Tuple.of(
                            join<T>(color<T>(node.left, RedBlackTree.Color.BLACK), node.value, split.first),
                            split.second
                        )
                    } else {
                        return Tuple.of(color<T>(node.left, RedBlackTree.Color.BLACK), color<T>(node.right,
                            RedBlackTree.Color.BLACK
                        ))
                    }
                }
            }

            private fun <T> unbalancedLeft(
                color: RedBlackTree.Color, blackHeight: Int, left: RedBlackTree<T>,
                value: T, right: RedBlackTree<T>, empty: Empty<T>,
            ): Tuple2<Node<T>, Boolean> {
                if (!left.isEmpty) {
                    val ln = left as Node<T>
                    if (ln.color == RedBlackTree.Color.BLACK) {
                        val newNode =
                            balanceLeft<T>(
                                RedBlackTree.Color.BLACK, blackHeight, ln.color(
                                    RedBlackTree.Color.RED
                                ), value, right, empty)
                        return Tuple.of(newNode, color == RedBlackTree.Color.BLACK)
                    } else if (color == RedBlackTree.Color.BLACK && !ln.right.isEmpty) {
                        val lrn = ln.right as Node<T>
                        if (lrn.color == RedBlackTree.Color.BLACK) {
                            val newRightNode = balanceLeft<T>(
                                RedBlackTree.Color.BLACK, blackHeight, lrn.color(RedBlackTree.Color.RED), value, right,
                                empty
                            )
                            val newNode = Node<T>(
                                RedBlackTree.Color.BLACK, ln.blackHeight, ln.left, ln.value, newRightNode,
                                empty
                            )
                            return Tuple.of(newNode, false)
                        }
                    }
                }
                throw IllegalStateException("unbalancedLeft($color, $blackHeight, $left, $value, $right)")
            }

            private fun <T> unbalancedRight(
                color: RedBlackTree.Color, blackHeight: Int, left: RedBlackTree<T>,
                value: T, right: RedBlackTree<T>, empty: Empty<T>,
            ): Tuple2<Node<T>, Boolean> {
                if (!right.isEmpty) {
                    val rn = right as Node<T>
                    if (rn.color == RedBlackTree.Color.BLACK) {
                        val newNode = balanceRight<T>(
                            RedBlackTree.Color.BLACK, blackHeight, left, value, rn.color(
                                RedBlackTree.Color.RED
                            ), empty)
                        return Tuple.of(newNode, color == RedBlackTree.Color.BLACK)
                    } else if (color == RedBlackTree.Color.BLACK && !rn.left.isEmpty) {
                        val rln = rn.left as Node<T>
                        if (rln.color == RedBlackTree.Color.BLACK) {
                            val newLeftNode = balanceRight<T>(
                                RedBlackTree.Color.BLACK, blackHeight, left, value, rln.color(
                                    RedBlackTree.Color.RED
                                ),
                                empty
                            )
                            val newNode = Node<T>(
                                RedBlackTree.Color.BLACK, rn.blackHeight, newLeftNode, rn.value, rn.right,
                                empty
                            )
                            return Tuple.of(newNode, false)
                        }
                    }
                }
                throw IllegalStateException("unbalancedRight($color, $blackHeight, $left, $value, $right)")
            }
        }
    }

    /**
     * The empty tree node. It can't be a singleton because it depends on a [Comparator].
     *
     * @param <T> Component type
    </T> */
    class Empty<T> internal constructor(val comparator: Comparator<T>) : RedBlackTree<T> {
        // Conditionally serializable
        //val comparator: Comparator<T> = comparator

        override fun color(): RedBlackTree.Color {
            return RedBlackTree.Color.BLACK
        }

        override fun comparator(): Comparator<T> {
            return comparator
        }

        override fun contains(value: T): Boolean {
            return false
        }

        override fun emptyInstance(): Empty<T> {
            return this
        }

        override fun find(value: T): Option<T> {
            return Option.none()
        }

        override val isEmpty: Boolean
            get() = true

        override fun left(): RedBlackTree<T> {
            throw UnsupportedOperationException("left on empty")
        }

        override fun right(): RedBlackTree<T> {
            throw UnsupportedOperationException("right on empty")
        }

        override fun size(): Int {
            return 0
        }

        override fun value(): T {
            throw NoSuchElementException("value on empty")
        }

        override fun toString(): String {
            return "()"
        }

    }
}